package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

/**
 * 归并排序(Merge Sort)算法完全依照了分治模式
 * 分解:将n个元素分成各含n/2个元素的子序列;
 * 解决:对两个子序列递归地排序;
 * 合并:合并两个已排序的子序列以得到排序结果
 * <p>
 * 和快排不同的是
 * 归并的分解较为随意
 * 重点是合并
 */
public class M05_归并排序_分治的完美诠释 {
    //归并过程中要用到的临时数组
    private static int[] helper = null;

    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 1, 20);
        helper = new int[arr.length];
        ArrayUtil.print(arr);
        mergeSort(arr, 0, arr.length - 1);
        ArrayUtil.print(arr);
    }

    /**
     * 归并排序入口
     *
     * @param A 待排序数组
     * @param p 左侧下标
     * @param r 右侧下标
     */
    private static void mergeSort(int[] A, int p, int r) {
        //当左侧下标小于右侧下标时，说明元素个数大于1个，需要继续进行划分
        if (p < r) {
            //找中间点
            int mid = p + (r - p) / 2;
            //递归划分左半区域，直到划分到只有一个元素
            mergeSort(A, p, mid);
            //递归划分右半区域，直到划分到只有一个元素
            mergeSort(A, mid + 1, r);
            //划分完成后需要合并
            merge(A, p, mid, r);
        }
    }

    /**
     * 归并方法
     *
     * @param A   原数组
     * @param p   左侧指针
     * @param mid 中间指针
     * @param r   右侧指针
     */
    private static void merge(int[] A, int p, int mid, int r) {
        //先把A中需要排序的数据(下标p到r)拷贝到helper临时数组中
        //参数：原数组，原数组起始位置，目标数组，目标数组起始位置，拷贝多少个元素
        System.arraycopy(A, p, helper, p, r - p + 1);
        ArrayUtil.print(helper);

        int left = p;//标记左半区域第一个未排序的元素
        int right = mid + 1;//标记右半区域第一个未排序的元素
        int current = p;//标记原数组待排序元素中第一个需要改动值的位置(直接对原数组进行修改)

        //左侧指针没到中间且右侧指针没到结尾时执行循环(左半区域还有元素并且右半区域也有元素时执行循环)
        while (left <= mid && right <= r) {
            //左半区域第一个剩余元素比右半区域第一个剩余元素更小时，把左半区域第一个元素插入到原数组
            if (helper[left] <= helper[right]) {
                A[current++] = helper[left++];
            } else {
                //右半区域第一个剩余元素更小时，把右半区域第一个元素插入到原数组
                A[current++] = helper[right++];
            }
        }
        //上述过程完成后，如果左侧区域元素还有剩余，需要将左侧区域剩余的元素插入到原数组中
        while (left <= mid) {
            A[current++] = helper[left++];
        }
        //如果右侧区域元素还有剩余，需要将右侧区域剩余的元素插入到原数组中
        while (right <= r) {
            A[current++] = helper[right++];
        }
    }
}
